class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        
        int n=nums.size();
        if(n==1){
            return;
        }
        int pos=n-2;
        while(pos>=0 && nums[pos]>=nums[pos+1]){
            --pos;
        }
        if(pos<0){
            reverse(nums.begin(),nums.end());
            return;
        }
        int sp=n-1;
        while(sp>pos && nums[sp]<=nums[pos]){
            --sp;
        }
        swap(nums[sp],nums[pos]);
        //cout<<pos+1<<endl;
        reverse(nums.begin()+pos+1,nums.end());
    }
};
